package main

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func minimumTotal(triangle [][]int) int {
	if len(triangle) == 0 {
		return 0
	}
	if len(triangle) == 1 {
		return triangle[0][0]
	}
	sums := [][]int{
		{triangle[0][0]},
	}
	for i, row := range triangle {
		if i == 0 {
			continue
		}
		sums = append(sums, make([]int, len(row)))
		for j, v := range row {
			if j == 0 {
				sums[i][j] = sums[i-1][j] + v
			} else if j == len(row)-1 {
				sums[i][j] = sums[i-1][j-1] + v
			} else {
				sums[i][j] = min(sums[i-1][j], sums[i-1][j-1]) + v
			}
		}
	}
	lastRow := sums[len(sums)-1]
	ret := 1<<31 - 1
	for _, v := range lastRow {
		if v < ret {
			ret = v
		}
	}
	return ret
}

func main() {
	tri := [][]int{
		{2},
		{3, 4},
		{6, 5, 7},
		{4, 1, 8, 3},
	}
	println(minimumTotal(tri))
}
